Longest Common Subsequence

Statement#

Suppose you are given two strings. You need to find the length of the longest common subsequence between these two strings.

A subsequence is a string formed by removing some characters from the original string, while maintaining the relative position of the remaining characters. For example, “abd” is a subsequence of “abcd”, where the removed character is “c”.

If there is no common subsequence, then return 0.

Let’s say you have the following two strings:

“cloud”
“found”

The longest common subsequence between these two strings is “oud”, which has a length of $3$ .

Constraints:

$1 <=$ str1.length $<= 500$
$1 <=$ str2.length $<= 500$
str1 and str2 contain only lowercase English characters.

Examples#

Python

usercode > main.py

Enter to Rename, Shift+Enter to Preview

Input #1

Input #2

Longest Common Subsequence

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Longest Common Substring dynamic programming pattern.

Naive approach#

A naive approach is to compare the characters of both strings based on the following rules:

If the current characters of both strings match, we move one position ahead in both strings.
If the current characters of both strings do not match, we recursively calculate the maximum length of moving one character forward in any one of the two strings i.e., we check if moving a character forward in either the first string or the second will give us a longer subsequence.
If we reach the end of either of the two strings, we return $0$ .

Let’s look at the following illustration to get a better understanding of the solution:

1 of 10

2 of 10

3 of 10

4 of 10

5 of 10

6 of 10

7 of 10

8 of 10

9 of 10

10 of 10

# Helper function with updated signature: i is current index in str1, j is current index in str2
def longest_common_subsequence_helper(str1, str2, i, j): 
    # base case
    if i == len(str1) or j == len(str2): 
        return 0
    # if current characters match, increment 1
    elif str1[i] == str2[j]:  
        return 1 + longest_common_subsequence_helper(str1, str2, i+1, j+1)
    
    # else take max of either of two possibilities
    return max(longest_common_subsequence_helper(str1, str2, i+1, j), longest_common_subsequence_helper(str1, str2, i, j+1))
def longest_common_subsequence(str1, str2):
    return longest_common_subsequence_helper(str1, str2, 0, 0)
# Driver code
def main():
    first_strings = ["qstw", "setter", "abcde", "partner", "freedom"]
    second_strings = ["gofvn", "bat", "apple", "park", "redeem"]
    # You can uncomment the lines below and check how this recursive solution causes a time-out 
    # first_strings.append("sjcneiurutvmpdkapbrcapjru")
    # second_strings.append("oidhfwepkxwebyurtunvidqlscmjbg")
    for i in range(len(first_strings)):
        print(i + 1, ".\t str1:",first_strings[i],"\n\t", \
                        "str2:", second_strings[i],"\n\n\t", \
                        "The length of the longest common subsequence is:", longest_common_subsequence(first_strings[i], second_strings[i])) \
                
        print("-" * 100)

Enter to Rename, Shift+Enter to Preview

Longest Common Subsequence using recursion

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of the naive approach is $O(2^{m+n})$ , where $m$ and $n$ are the lengths of the two strings respectively. This is because, at each point, we can have a maximum of two possibilities: either move one character ahead in the first string or in the second string.

Space complexity#

As there are $O(n + m)$ recursive calls, and each call stores its data on the stack, the space complexity of this approach is $O(n + m)$ .

Optimized Solution using dynamic programming#

Now, let’s improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in an array. In the recursive approach, the following two variables kept changing:

The index i, used to keep track of the current character in str1.
The index j, used to keep track of the current character in str2.

We will use a 2-D table, dp, with $n$ rows and $m$ columns to store the result at any given state. At any later time, if we encounter the same subproblem, we can return the stored result from the table with an $O(1)$ lookup, instead of recalculating that subproblem.

Let’s look at the following illustration to get a better understanding of the solution:

# Helper function with updated signature: i is current index in str1, j is current index in str2
def longest_common_subsequence_helper(str1, str2, i, j, dp): 
    # base case
    if i == len(str1) or j == len(str2): 
        return 0
    elif dp[i][j] != -1:
        return dp[i][j]
    # if current characters match, increment 1
    elif str1[i] == str2[j]:  
        dp[i][j] = 1 + longest_common_subsequence_helper(str1, str2, i+1, j+1, dp)
        return dp[i][j]
    
    # else take max of either of two possibilities
    dp[i][j] = max(longest_common_subsequence_helper(str1, str2, i+1, j, dp), 
                   longest_common_subsequence_helper(str1, str2, i, j+1, dp))
    return dp[i][j]
def longest_common_subsequence(str1, str2):
    n = len(str1)
    m = len(str2)
    dp = [[-1 for x in range(m)] for y in range(n)]
    return longest_common_subsequence_helper(str1, str2, 0, 0, dp)
# Driver code
def main():
    first_strings = ["qstw", "setter", "abcde", "partner", "freedom"]
    second_strings = ["gofvn", "bat", "apple", "park", "redeem"]
    # You can uncomment the lines below and check how this recursive solution causes a time-out 

Enter to Rename, Shift+Enter to Preview

Longest Common Subsequence using memoization

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

Let’s think of this in terms of the keyspace mapped by the tuple of i and j. For strings of length $m$ and $n$ , i can go from $0$ to $m$ , while j can go from $0$ to $n$ . Therefore, the total number of unique subproblems to evaluate and store are $(m \times n)$ . So, the time complexity of this approach is reduced to $O(m \times n)$ because we avoid redundant calculations by storing all the intermediate results in a 2-D array.

Space complexity#

We now need $O(n \times m)$ space in memory to store intermediate values in the table.

Bottom-up solution#

The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic problems. We first make a 2-D array of size $[(m+1) \times (n+1)]$ , where $n$ is the length of str1 and $m$ is the length of str2. This array is initialized to $0$ . We need the first row and column to be $0$ for the base case. Any entry in this array given by dp[i][j] is the length of the longest common subsequence between str1 up to $i^{th}$ position and str2 up to the $j^{th}$ position.

As we saw in the recursive algorithm, when the characters matched, we could simply move one position ahead in both strings and add one to the result. This is exactly what we do here as well. We add $1$ to the previous diagonal result. In case we have a mismatch, we need to take the maximum of two subproblems:

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

We could either move one position ahead in str1 (the subproblem dp[i-1][j]), or we could move one step ahead in str2 (the subproblem dp[i][j-1]). In the end, we have the optimal answer for str1 and str2 in the last position, i.e., dp[n][m].

Let’s look at the following illustration to get a better understanding of the solution:

def longest_common_subsequence(str1, str2):
    n = len(str1)   # length of str1
    m = len(str2)   # length of str2
    rows = n + 1
    cols = m + 1
    # Initializing the 2-D table, filling the first row and column with all 0s
    dp = [[0 if (i == 0 or j == 0) else -1 for i in range(cols)] for j in range(rows)]
    # Iterating to fill the table
    for i in range(1, rows):           
        # calculate new row (based on previous row i.e. dp)
        for j in range(1, cols):
            # if characters at this position match, 
            if str1[i-1] == str2[j-1]:    
                # add 1 to the previous diagonal and store it in this diagonal
                dp[i][j] = dp[i-1][j-1] + 1 
            else:
                # If the characters don't match, fill this entry with the max of the
                # left and top elements
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]) 
    return dp[n][m]
# Driver code
def main():
    first_strings = ["qstw", "setter", "abcde", "partner", "freedom"]
    second_strings = ["gofvn", "bat", "apple", "park", "redeem"]
    # Let's uncomment this to see the benefit of using dynamic programming with tabulation
    # first_strings.append("sjcneiurutvmpdkapbrcapjru")

Enter to Rename, Shift+Enter to Preview

Longest Common Subsequence using tabulation

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we created a 2-D array to store the results of subproblems that would be used later on, therefore, the time complexity of this approach will also be $O(n \times m)$ .

Space complexity#

We need $O(n \times m)$ space in memory to store the intermediate values.

Can we do better?#

You must have noticed in the above algorithm that to fill up a row, we only require the previous row’s values; that is, for filling the row against the $i^{th}$ character, we require the values from the previous row representing the $(i-1)^{th}$ character. Therefore, there is no point in storing all the previous $(i-2)$ rows.

We can further improve this approach by using a 1-D array of length $(m + 1)$ instead of creating a table. Next, we update this array for each element using the same calculation which we used earlier.

The time complexity would remain the same, $O(n \times m)$ , because we still have to do the calculation for each element. The space complexity, however, reduces to $O(m)$ since we are only maintaining an array of the size $(m + 1)$ .

No.	str1	str2	Length
1	"bald"	"bad"	3
2	"nocturnal"	"nick"	2
3	"card"	"tissue"	0

Statement#

Examples#

Try it yourself#

Solution#

Naive approach#

Time complexity#

Space complexity#

Optimized Solution using dynamic programming#

Top-down solution#

Time complexity#

Space complexity#

Bottom-up solution#

Time complexity#

Space complexity#

Can we do better?#